1. Field of the Invention
This invention relates generally to the field of adaptive transversal filters such as those used in echo cancellers and more particularly to an adaptive echo canceller having dynamically positioned sparse adaptive filter taps and to a method for allocating and updating the positions of the taps.
2. Background of the Invention
Impedance mismatches and other circuit discontinuities in telephone lines often result in the presence of echoes on such lines. These mismatches generally occur at 2 wire to 4 wire and 4 wire to 2 wire transitions. Such echos produce confusion in the case of voice communication and may cause data errors in the case of data communication if the echo is severe enough. This is of course undesirable in voice communications, but may be intolerable in data communication. In full duplex or even half duplex analog (modem) and digital data communications circuits, such echoes are interpreted by a receiver as noise which can corrupt incoming received signals causing reduced data throughput and/or data errors.
Such echo signals have been canceled in the prior art with echo cancellers such as that shown in FIG. 1. In this arrangement, which is similar to that presented in the Bell System Technical Journal, Vol. XLVI, Number 3, March 1967 entitled "An Adaptive Echo Canceller" by Shondi et al, a signal source 10 produces a digital signal which is converted to an analog signal by digital to analog converter 12 prior to application to a hybrid transformer circuit 14. Hybrid 14 is coupled to a two wire transmission line 16 which is also used to receive incoming signals which are applied to an analog to digital converter 18. The analog to digital converter 18 passes the received signals on to a receiver 20 for processing.
The remaining circuitry comprises an echo canceller which is in the form of a transversal filter (generally) which is placed between the transmit and receive paths as shown. The echo canceller includes a tapped delay line or shift register 24 coupled to the output of signal source 10. The shift register has periodic output taps which are coupled to a plurality of multipliers 28. The multipliers 28 are also coupled to a tap coefficient memory 32 which stores the tap weights or tap coefficients for the transversal filter. These tap weights may represent the impulse response of the transmission line 16. The outputs of the multipliers 28 are summed together at an adder 36 producing a replica of the echol signal returned by the transmission line in response to the transmitted signal from signal source 10. This, of course, assumes that the echo signal may be replicated by a weighted sum of delayed input signals from signal source 10. This echo replica is in the form of: ##EQU1## Where: N=a tap number
K=the number of taps in the echo canceller PA1 T=the sampling interval PA1 C.sub.N =tap weight at position N PA1 X.sub.N =sample of output of signal source at tap N PA1 e=echo replica. PA1 Y=the received signal after echo cancellation PA1 n=noise PA1 e=the echo signal PA1 .epsilon.=the error between the echo replica and the actual echo.
This echo replica e is subtracted at subtracter 40 from the incoming signal at the output of the analog to digital converter 18 in order to cancel the echo signal so that only the transmitted signal plus noise and an error signal (from imperfect echo cancellation) remain as follows: ##EQU2## Where: Y=the desired transmitted signal
Such echo signals (impulse responses) may take on many forms with the most common being that of a near end echo (resulting from discontinuities and mismatches at a local telephone office) plus far end echoes (resulting from such discontinuities or mismatches at remote telephone offices). An example of such echoes is shown in FIG. 2 where the near end echo is represented by echo 50 and the far end echo is represented by echo 52.
In the example of FIG. 2, near end echo 50 is shown to be approximately the same magnitude as echo 52. Another possibility is shown in FIG. 3 with an echo 60 representing the near end echo and a somewhat smaller echo 62 representing the far end echo. Of course, an unlimited number of other possible echo situations exist and those presented here are only presented by way of example.
One of the more common techniques for dealing with the combination of near end plus far end echoes is described in U.S. Pat. No. 4,464,545 to Werner. This echo canceller structure utilizes a near end sub-canceller to cancel the near end echo and a far end sub-canceller to cancel to the far echo. The two sub-cancellers are separated by a bulk delay unit to account for the silent period of no echos between the near end and far end echoes. This structure, in order to be optimally effective, requires knowledge of when in time an echo is likely to occur and how long each echo will last so that the length of the near end and far end echo canceller and the duration of the bulk delay may be established. Also, in the case of the echo of FIG. 3, computational noise may be generated by virtue of too many taps used to cancel the relatively small echo 62.
U.S. Pat. No. 4,582,963 improves upon this echo canceller arrangement by allowing the bulk delay unit to be variable. In this patent, the variable bulk delay allows for varying distances between the local and remote offices so that the near end canceller and far end canceller can be more optimally situated in time to enhance the likelihood of good cancellation of both the near end and far end echoes.
Unfortunately, neither of the arrangements shown in the abovereferenced patents can account for an echo signal such as that shown in FIG. 4. In this echo signal, a near end echo 70 is followed by an intermediate echo 72 which is then followed by a far end echo 74. According to published studies by Bell Telephone Laboratories, intermediate echoes occur in approximately 30% of all long distance connections. The echo cancellers of Werner and U.S. Pat. No. 4,582,963 to Danstrom are unable to cope with such intermediate echoes thus, substantial corruption of data or voice signals may occur as a result.
A paper published at the I.C.A.S.S.P. 86 in Tokyo entitled "A Tap Selection Algorithm For Adaptive Filters", Kawamura et al., describes a tap adaption algorithm entitled "Scrub Taps Waiting In a Queue" or "STWQ" which may allow a digital adaptive filter to ultimately adapt to such an intermediate echo 22 as shown in FIG. 3. Unfortunately, such an algorithm has another drawback encountered by the two previously mentioned types of echo cancellers. Namely, that it is undesirable for an echo canceller to operate when there is no echo. Running an echo canceller under such circumstances merely creates computational noise as a result of finite word length accuracy in the digital transversal filter. This may actually hinder the reception of data in a marginal line. This paper also suggests that the canceller is best adapted from a random or evenly distributed initial allocation of the fixed number of taps which are allowed.
It is therefore desirable to provide a digital echo canceller structure which overcomes many of the drawbacks associated with conventional echo canceller structures.